1. The Field of the Invention
The field of the present invention is that of protecting critical segments of code in an environment where multiple streams of executable instructions may be operating through the critical segment. This occurs typically in multi-tasking operating systems and special structures known as "locks" are used to protect the critical code sections. Particularly, the present invention treats ways of reducing situations where a stream of executable instructions must "wait" on a lock or other protection mechanism that results in degraded system performance.
2. Present State of the Art
In an environment where multiple streams of executable instructions operate independent of one another, such as in a multi-tasking and multi-threaded operating system, certain operations must be performed by a stream of executable instructions to the exclusion of other streams of executable instructions. It is important in some instances to manipulate data in such a manner that only one processing thread operates thereon with no other stream of executable instructions disturbing the data until the operation is finished. For example, when updating a data structure that is common to the multiple streams of executable instructions, it is important that only one stream be making any modifications at a time or otherwise have write-access so that the integrity of the data structure is maintained. In some scenarios, read-access may occur while write-access must only occur in a protected mode.
One mechanism that is used to protect such critical areas of code is known as a "lock." A lock must be held or acquired in order to proceed through the critical area or segment of code. After passing through the critical segment, the lock will be released and another executable stream may acquire or hold the lock. If one executable stream holds a lock and another attempts to access or acquire the lock that is already held, the second executable stream will in some way "wait" upon the lock until it is released by the first executable stream. Such waiting can cause degraded system performance, and it is desirable to reduce such waiting as much as possible.
Since the lock acts as a gate to allow only one stream of executable instructions to operate through a critical segment at any one time, many executable streams vying for a given lock can lead to "contention" for that lock. As a general rule, the more often a given lock needs to be accessed during the course of normal processing for a given application program or system having multiple streams of executable instructions, the greater the potential for lock contention.
A stream of executable instructions may wait on a lock in a variety of different manners depending on the system implementation and nature of the stream of executable instructions. For example, in the Windows NT operating system by Microsoft a stream of executable instructions may be a thread in user mode that will sleep upon encountering an unavailable lock that will in turn "awaken" when the lock later becomes available. As another example, in the Windows NT environment kernel mode operations on a multi-processor system will encounter "spin" locks that control access to common resources such as memory. Therefore, when a spin lock is encountered that is held by another stream of executable instructions on another processor, the encountering processor and stream of executable instructions will simply spin in place and be completely blocked from doing productive work until the spin lock is released.
One situation where lock contention may become a serious performance issue is where a common data structure representing a database known as a database or database structure contains objects that maybe used by one or many different streams of executable instructions. Access to the database structure or a relevant portion of the database structure is controlled by a lock known as a "global lock." This may be a global lock for the entire database structure or for a relevant portion thereof. For example, if employee record objects were contained in a database structure, 26 separate locks could be used to control relevant portions of the database structure based on the first letter of each employee's last name.
Objects may be created, placed in the database, and used as necessary by one or more streams of executable instructions. The objects may be deleted from the database structure and destroyed when they are not longer needed. Since the multiple streams of instructions may be simultaneously operating, a global lock is used to control access to the database structure when creating the object and inserting it into the database structure, searching the database structure to use the object, or removing the object from the database structure and destroying it as part of a delete operation.
Efficient programming techniques mandate that a global lock be held for the minimum of time possible in order to achieve the desired function in order to reduce lock contention amongst the different streams of executable instructions that may need relatively simultaneous access to the database structure. Additionally, a reference count is used to track the life cycle of a particular object. The reference count is initialized at creation to a value of one and will be incremented when a stream of executable instructions begins using the object and decremented when a stream of executable instructions is finished using the object. There will be a final decrementation of the reference count when deleting the object that the reference count value will be zero, signifying that the object is no longer in the database structure and thus can be used no longer. In other words, when an objects reference count reaches zero, the object will be destroyed.
FIGS. 1-4 show how conventional methods are used in a typical scenario that may result in excessive contention for a global lock. FIGS. 1-3 are flow charts corresponding to the operations of creating and placing an object in a database structure, using an object, and removing an object from a database structure and destroying it, respectively, while FIGS. 4A-4F show the creation, placement in a database structure, use, removal from a database structure, and destruction of two objects according to the flow charts in FIGS. 1-3.
Referring to FIG. 1, a flow chart showing the processing steps taken by a stream of executable instructions, such as a process thread, to create an object and place it in a database structure are shown. After beginning processing at step 20, the object is allocated at step 22 with any necessary storage requirements. One variable associated with the object is a reference count or ref count that will track the life of the object. As long as the reference count value is not zero, the object will not be destroyed since it has not been deleted or, if deleted, a stream of executable instructions is still processing the associated object.
The object will be initialized into a known state and the reference count assigned a value of one at step 24. At this point, the object is ready to be inserted into the database or database structure, such as a tree structure, queue structure, linked list structure, etc.
At step 26, the global lock is acquired, thereby blocking any other stream of executable instructions from interfering with the insertion operation. The object is inserted into the database at step 28. This must be done while the global lock is held so that pointers in a linked list or other data structure will not be inadvertently corrupted or read before they are in a stable condition. Finally, the global lock is released at step 30 and processing for the insertion operation ends at step 32.
Referring now to FIG. 2, processing steps taken by a stream of executable instructions for using an object located in a database or database structure are shown. Processing begins at step 34 and the global lock is acquired at step 36 in order to access the database containing object.
At step 38, the database structure is searched for the desired object and a test is made at step 40 to determine whether the object was found. If the object was not found, then the global lock is immediately released at step 32 and processing ends at step 34.
If the desired object is found within the database as determined at step 40, however, processing continues and the reference count for the object is incremented at step 46 in order to indicate that the object is currently being used by another stream of executable instruction and, therefore, should not be destroyed until after the stream is finished if a delete operation occurs before processing is completed.
Once the desired object has been located and the corresponding reference count for that object incremented, it is safe for other streams of executable instructions to have write-access to the object's reference count and to also access the database. Therefore, the global lock is released at step 48 thereby allowing other streams of executable instructions to access the database structure.
The object is processed as necessary by the stream of executable instructions at step 50. Note that if critical data areas are accessed as part of the object processing, other locks, such as an object lock, may need to be acquired.
In any case, once processing is complete by the particular stream of executable instructions, the global lock is acquired once again at step 52 in order to process the reference count value of the object without interference from other streams of executable instructions. First, the reference count is decremented at step 54 in order to indicate that the particular stream of executable instructions has finished processing the object.
Next, the reference count value is checked or remembered at step 56 after being decremented at step 54. This checking step 56 will be used to determine whether or not the object should be destroyed. The global lock is released at step 58 so that other streams of executable instructions can have access to the reference counts for the various objects as well as the database structure wherein the objects are contained.
In conjunction with step 56, a test is made at step 60 to determine whether the reference count value is equal to zero. If the reference count value is not zero at this particular point in time, then the object should remain in existence because it has not been explicitly deleted or another stream of executable instructions continues processing an object that has been indicated for deletion. The processing will then end at step 44.
If the reference count value is equal to zero as determined at step 60, this indicates that no objects are processing this particular object and that is has been explicitly deleted and is now therefore ready to be destroyed. In other words, even though the object had been previously and explicitly deleted, it remained in existence so that the current stream of executable instructions could finish its processing before actually destroying the object at steps 62 and ending processing at step 44. The different scenarios showing the different ways in which an object may be destroyed by either the deletion operation processing or by the stream of executable instructions actually using the object will be shown hereafter in more detail in connection with FIGS. 4A-4F.
Referring now to FIG. 3, a flow chart showing the processing steps for the deletion of an object from a database structure as done in the prior art is shown. By performing the delete operation on a particular object, no other streams of executable instructions will be able to use the object and once the last of any stream of executable instructions is finished processing the particular object, the object will be destroyed. That last stream of executable instructions may be the stream actually doing the delete operation, and if so, that particular stream will actually destroy the object.
Processing begins at step 64 and the global lock is acquired at step 66 in order to access the database structure wherein the object is held. At step 68, the object is found and removed from the database structure though not destroyed at this point.
The object reference count is decremented at step 69. The delete operation decrementation of the object reference count corresponds to the original initialization of the reference count to one so that if no streams of executable instructions are using the object, the reference count will be decremented to zero. The reference count value is checked at step 70 before releasing the global lock at step 72.
A comparison is made at step 74 to see whether the reference count value checked at step 70 is equal to zero. If it is not equal to zero, then the object is still being used by another stream of executable instructions and should not yet be destroyed, and processing will end at step 76. In this scenario, one of the streams of executable instructions that is still using the object will eventually destroy the object as explained previously in connection with step 62 of FIG. 2.
If the reference value is equal to zero as determined at step 74, the object will be destroyed at step 78 before processing ends at step 76. This occurs because no streams of executable instructions, including the current stream, are currently processing the object so that it is then destroyed at step 78.
Referring now to FIGS. 4A-4F, the life cycle of two objects is shown, one where the object is destroyed by the delete operation and another where the object is destroyed by a use operation that necessarily continues processing the object even after the object has been deleted by another stream of executable instructions.
Referring to FIG. 4A, two objects, object A 64 and B 66, are initially created at step 22. After acquisition of the global lock, the objects can be placed into a global data structure, such as global list 68, and have there respective reference count values initialized to one as shown in FIG. 4B. The global lock can then be released and the global list 68 can be accessed by other streams of executable instructions.
Referring to FIG. 4C, the state of object A 64 and object B 66 are shown when two separate streams of executable instructions are currently processing each of the respective objects, one processing object A 64 and the other processing object B 66. This is indicated by the reference count value being two for each respective object, object A 64 and object B 66. This would normally occur at step 46 of the flow chart shown in FIG. 2 when a stream of executable instructions would have incremented the reference count thereby indicating its use of the respective object. Note that such incrementation would occur while the global lock is held.
Referring now to FIG. 4D, the stream of executable instructions that had been processing object A 64 has finished thereby leaving the reference count value at one while the stream of executable instructions that was processing object B 66 continues processing and has not yet finished. This sets up a situation where one object has no stream of executable instructions operations or processing thereon while the other object continues to have a stream of executable instructions operating or processing thereon.
Referring now to FIG. 4E, the results of a delete operation for both object A 64 and object B 66 are shown. By following the processing steps shown in FIG. 3, object A 64 is first removed from the data structure and has the reference count value decremented to zero; this occurring while the global lock is held. Next, since the reference count value is determined to be zero at step 74 of FIG. 3, the object is destroyed at step 78 as indicated by the X through object A 64.
Object B 66 also has a delete operation performed thereon and is therefore removed from the global list 68 and has its reference count value decremented to one while the global lock was held. Object B 66 is not destroyed, however, since a stream of executable instructions continues to use the object during processing.
Referring now to FIG. 4F, the destruction of object B 66 is shown as it will occur after the stream of executable instructions that was using the object has terminated. When finished, the stream of executable instructions decrements the reference count value to zero thereby allowing that particular stream of executable instructions to complete the desired deletion of the object by destroying object B 66. is destruction would occur at step 62 of the flow chart shown in FIG. 2. Note that it is the stream of executable instructions that was using the object rather then the stream of executable instructions that deleted the object that actually destroys the object B 66. This is shown in FIG. 4F by an X drawn through object B 66.
One situation where it is common to observe the above-illustrated scenarios occurs when objects represent visual windows of an application as part of the application's user interface. For example, an e-mail application may have separate windows for each message that is being viewed besides the main application window. In this case, the original application window could be exited thereby signifying the termination of the application as a whole. As part of its termination sequence, the application would delete all objects out of the global list. This will leave situations where the user has not necessarily finished viewing the messages so that the application will continue running until the user signifies being finished viewing messages by manually exiting the individual windows. Such exiting will indicate the end of processing by each separate stream of executable instructions that in turn allows the object representing the window to be destroyed as has been explained previously. Finally, when all the windows have been manually exited, no objects will remain in the global list and the application itself can terminate and be destroyed.
Within the context of the aforementioned background, a serious problem results as the number of objects located in the global database structure becomes very large, or if many different streams of executable instructions desire to operate on a particular object. Under these situations there becomes a large amount of contention for the global lock since many references may be made to the global database structure, such as the global list or queue 68, that holds the objects and must be accessed while the global lock is held. In some cases, the contention for the global lock may cause such delay and wasted CPU cycles that there is excessive overhead on system performance. It is therefore desirable to reduce such lock contention so that system performance is not adversely impacted.
One way of relieving global lock contention is to use a second lock to also control access to the single reference count. Typically, this second lock would be an object lock that is controlling access to the object itself. In this scenario, at the commencement of processing an object, the global lock would be accessed as before followed by an acquisition of object lock while the global lock is being held. The reference count would be adjusted as explained previously and the locks could be released in reverse order so that the object lock acquisition and release occurs entirely while the global lock is held. If the object lock were needed for processing the object, it would have to be required. After processing the object, the second lock, such as the object lock, would be used alone to protect updating the single reference count. This would reduce the global lock contention but requires more lock acquisitions that take CPU cycles and imposes a special ordering on the two locks.
While use of different locks and special ordering between the different locks may be used to alleviate the global lock contention problem somewhat by reducing the number of global lock acquisitions, such schemes require special ordering constraints between the acquisition and release of different locks. Too much ordering constraint may introduce errors in software since such constraints are fully implemented by the programmer and are subject to human error.
What is needed is a way to reduce global lock contention that will minimize global lock acquisitions without introducing burdensome lock ordering constraints. By minimizing the number of global lock acquisitions, fewer streams of executable instructions will be required to wait for the lock thereby improving overall system processing efficiency.